package com.github.yangyishe.p300;

import java.util.Arrays;

/**
 * 289. 生命游戏
 * https://leetcode.cn/problems/game-of-life/?envType=study-plan-v2&envId=top-interview-150
 *
 * 根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
 *
 * 给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
 *
 * 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
 * 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
 * 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
 * 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
 * 下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
 * 输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
 * 示例 2：
 *
 *
 * 输入：board = [[1,1],[1,0]]
 * 输出：[[1,1],[1,1]]
 *
 *
 * 提示：
 *
 * m == board.length
 * n == board[i].length
 * 1 <= m, n <= 25
 * board[i][j] 为 0 或 1
 */
public class Problem289 {
    public static void main(String[] args) {
        int[][] board=new int[][]{
                {1,1},
                {1,0},
        };
        Problem289 problem289 = new Problem289();
        problem289.gameOfLife(board);

        for (int[] ints : board) {
            System.out.println(Arrays.toString(ints));
        }
    }

    /**
     * 思路:
     * 1. 创建一个细胞权值矩阵, 用来表示当前情况一个单元格周围细胞数量
     * 创建方法: 创建空矩阵后, 遍历每一个单元格, 对该单元格的周围临近值+1
     * 2. 根据细胞权值矩阵, 修改细胞矩阵的下个状态
     *
     * 注:
     * 后续做矩阵相关题目, 使用width和height表示矩阵的宽度和高度. row和col表示矩阵的第几行和第几列
     * 这样不容易弄混
     *
     * @param board
     */
    public void gameOfLife(int[][] board) {
        int h=board.length;
        int w=board[0].length;

        // 构建权值矩阵
        int[][] powers=new int[h][w];
        for(int r=0;r<h;r++){
            for(int c=0;c<w;c++){
                if(board[r][c]>0){
                    if(r-1>=0){
                        if(c-1>=0){
                            powers[r-1][c-1]++;
                        }
                        powers[r-1][c]++;
                        if(c+1<w){
                            powers[r-1][c+1]++;
                        }
                    }
                    if(c-1>=0){
                        powers[r][c-1]++;
                    }
                    if(c+1<w){
                        powers[r][c+1]++;
                    }
                    if(r+1<h){
                        if(c-1>=0){
                            powers[r+1][c-1]++;
                        }
                        powers[r+1][c]++;
                        if(c+1<w){
                            powers[r+1][c+1]++;
                        }
                    }
                }
            }
        }

        // 对细胞矩阵处理
        for(int r=0;r<h;r++){
            for(int c=0;c<w;c++){
                if(board[r][c]==1){
                    if(powers[r][c]<2||powers[r][c]>3){
                        board[r][c]=0;
                    }
                }else{
                    if(powers[r][c]==3){
                        board[r][c]=1;
                    }
                }

            }
        }

    }
}
